package com.demo.java.OD101_150.OD147;

import java.util.HashMap;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最少数量线段覆盖 or 区间交叠问题】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145740077
 */
public class OdMain {
    public static void main(String[] args) {
        // 使用 try-with-resources 来确保 Scanner 在使用完后自动关闭
        try (Scanner scanner = new Scanner(System.in)) {
            // 读取输入的点的数量 n
            int n = Integer.parseInt(scanner.nextLine());

            // 创建一个二维数组来存储每个点的区间 [start, end]
            int[][] points = new int[n][2];

            // 读取每个点的起始和结束坐标，存入 points 数组
            for (int i = 0; i < n; i++) {
                // 分割输入的每一行，获取点的起始值和结束值
                String[] split = scanner.nextLine().split(",");
                points[i] = new int[]{Integer.parseInt(split[0]), Integer.parseInt(split[1])};
            }

            // 调用 solution 方法来计算结果
            int res = solution(n, points);

            // 输出最终结果
            System.out.println(res);
        }
    }

    // 解决问题的核心方法，返回剩余点的数量
    private static int solution(int n, int[][] points) {
        // 创建一个 HashMap 来记录点的出现频率
        HashMap<Integer, Integer> line = new HashMap<>();

        // 将所有点的信息加入到 HashMap 中，统计区间范围内每个点的出现次数
        addPointsToMap(points, line);

        // 记录被删除的点的数量
        int del = 0;

        // 遍历所有的点，检查哪些点可以被删除
        for (int i = 0; i < n; i++) {
            int[] point = points[i];
            // 如果该点可以被删除，则执行删除操作
            if (isDeletable(point, line)) {
                // 删除点的操作
                removePointsFromMap(point, line);
                // 记录已删除的点
                del++;
            }
        }

        // 返回剩余的点的数量，即总点数减去删除的点数
        return n - del;
    }

    // 将所有点的信息加入到 HashMap 中，统计区间内的点的出现次数
    private static void addPointsToMap(int[][] points, HashMap<Integer, Integer> line) {
        // 遍历所有的点
        for (int i = 0; i < points.length; i++) {
            int[] point = points[i];
            // 对于每个区间 [start, end]，遍历区间内的每个点
            for (int j = point[0]; j <= point[1]; j++) {
                // 更新该点出现的次数，若该点不存在则默认值为 0
                line.put(j, line.getOrDefault(j, 0) + 1);
            }
        }
    }

    // 判断某个点是否可以被删除
    private static boolean isDeletable(int[] point, HashMap<Integer, Integer> line) {
        // 遍历点的区间 [start, end]
        for (int j = point[0]; j <= point[1]; j++) {
            // 如果某个点的出现次数小于等于 1，则说明该点不可以删除
            if (line.get(j) <= 1) {
                return false;
            }
        }
        // 如果区间内的所有点出现次数大于 1，则返回 true，表示可以删除
        return true;
    }

    // 从 HashMap 中移除点的信息
    private static void removePointsFromMap(int[] point, HashMap<Integer, Integer> line) {
        // 遍历点的区间 [start, end]
        for (int j = point[0]; j <= point[1]; j++) {
            // 减少该点的出现次数
            line.put(j, line.get(j) - 1);
        }
    }

}